This disclosure relates generally to data decoding, and more particularly to optimizing error floor performance of finite-precision layered decoders of low-density parity check (LDPC) codes.
With the continuing demand for high-reliability transmission of information in digital communication and storage systems, and with the rapid increase in available computational power, various coding and decoding techniques have been investigated and applied to increase the performance of these systems. One such coding technique, low-density parity check (LDPC) coding, was first proposed in the 1960s, but was not generally used until the 1990s when researchers began to investigate iterative coding and decoding techniques.
LDPC codes are among the few known error control coding techniques capable of transmitting information at a rate close to the Shannon limit or channel-capacity. LDPC codes may be used in the transmission of information on media, or channels, with or without memory. LDPC coding techniques are generally iterative in nature, and may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
As used herein, “finite precision” refers to a property of an object that signifies that the object either may contain information that may be represented by a finite set of symbols or that the object may perform computations on information represented by a finite set of symbols.
An iterative decoder for use with channels without memory may include an error correcting code (ECC) decoder. In performing decoding, the information from the channel may be passed to the ECC decoder for use in the decoding operation. An iterative decoder for use with channels with memory may include a soft-input soft-output (SISO) channel detector in addition to the ECC decoder. An iterative decoder may alternate between use of a SISO channel detector and ECC decoder to decode data. The information from an iteration of the SISO channel detector may be passed to the ECC decoder for use in the next ECC decoding iteration, and vice versa. Through this iterative process, data reliability is improved.
An iterative decoder may decode LDPC codes using an iterative message passing algorithm, such as a min-sum decoding algorithm. Such algorithms may decode a received codeword using an iterative process, in which each iteration includes two update steps. In the first update step, messages may be passed from some (or all) check nodes to some (or all) variable nodes, and in the second update step, messages may be passed from some (or all) variable nodes to some (or all) check nodes. The update steps may be scheduled in a serial (layered) or flooding fashion. A layered update schedule may provide similar performance with half the number of iterations as compared to a flooding decoding schedule. Details about a layered decoder can be found in the following reference “A 640-Mb/s 2048-Bit Programmable LDPC Decoder Chip”, in IEEE Journal of Solid State Circuits, March 2006. An iterative decoder which uses a layered update schedule for the message passing algorithm may be referred to as a layered iterative decoder.
The performance capability of a coding scheme, such as a LDPC coding scheme, is often described by the code's performance curve. The performance curve is a plot of signal-to-noise ratios (SNR) vs. Bit Error Rate (BER), or Sector Error Rate (SER). The performance curve of LDPC codes generally includes two regions: a waterfall region and an error floor region (see FIG. 6). In the waterfall region, the code's BER or equivalently, SER, decreases rapidly with improvements in SNR. However, in the high SNR operating region, the BER/SER plateaus to an error floor, meaning that further improvements in channel condition would not lead to significantly lower BER/SER.
Messages that are passed in the message passing algorithm, used by the iterative decoder, may be of a finite precision. If the messages passed have insufficient precision or precision that is not optimized, the iterative decoder may have the drawback of producing two types of errors that results in higher error floors, which is highly undesirable. These two types of errors are: 1) near-codeword failures and 2) catastrophic errors also known as propagating errors of propagating failures. Near-codeword failures in iterative decoders that do not use properly selected or optimized message precisions may occur more frequently than they would in iterative decoders that use properly selected or optimized message precisions. Details about near-codeword failures can be found in “Weaknesses of Margulis and Ramanujan-Margulis Low-Density Parity-Check Codes” in Electronic Notes in Theoretical Computer Science 2003. Catastrophic errors may lead to increased BER/SER at high SNR values. Moreover, an increased BER/SER at high SNR values may lead to degraded application performance and/or a lowered data transmission rate.
Many communication channels utilizing iterative encoders and iterative decoders operate in the error floor region of the performance curve of the LDPC code. Due to the fact that error floors tend to be very low, e.g. in some instances the error floor is observed at SER=1e−9, at SER=1e−12, or lower, it might not be feasible to reliably simulate error floor performance of a LDPC code. As a consequence, simulations in the waterfall region are typically relied upon to carry out performance/complexity studies for implementations of iterative decoders using messages. It is important to note, however, that neither the effects of near-codeword failures nor the effects of catastrophic errors are likely to be observed in the waterfall region of the performance curve of a LDPC code. Therefore, iterative decoders that are configured based on the performance curve of the LDPC code in the waterfall region (i.e. BER/SER performance at lower SNRs) may use precisions that may not be appropriate or sufficient for the error floor region of the performance curve of the LDPC code. This can lead to suboptimal implementations of an iterative decoder for LDPC codes.
Iterative decoders which use a message passing algorithm with optimized message precisions (or with a modified decoding update rule) may avoid a high probability for near-codeword faulures and may produce fewer catastrophic errors. This may lead to decreased BER/SER at various SNR values. Therefore, it would be desirable to provide layered iterative decoders which use a message passing algorithm with optimized message precisions based on the error floor region of the performance curve of a LDPC code. The increased decoding performance in the error floor region of these types of decoders may lead to improved application performance and/or larger data transmission rates.